package com.lft.tree05.heap_sort;

import java.util.ArrayList;
import java.util.List;

/**
 * 最大堆
 */
public class MaxHeapDemo {
}

class MaxHeap<E extends Comparable<E>> {
	private List<E> data;
	
	public MaxHeap() {
		this.data = new ArrayList<>();
	}
	
	public MaxHeap(int capacity) {
		this.data = new ArrayList<>(capacity);
	}
	
	/**
	 * 返回堆中元素的个数
	 * @return
	 */
	public int size() {
		return data.size();
	}
	
	/**
	 * 判断堆是否为空
	 * @return
	 */
	public boolean isEmpty() {
		return data.isEmpty();
	}
	
	/**
	 * 使用数组表示的二叉堆中我们可以使用索引找到父节点索引，左右子节点的索引。
	 * @param index
	 * @return
	 */
	private int parentIndex(int index) {
		assert index >= 1;
		return (index - 1) / 2;
	}
	
	private int leftChildIndex(int index) {
		return index * 2 + 1;
	}
	
	private int rightChildIndex(int index) {
		return index * 2 + 2;
	}
	
	/**
	 * 添加元素，sift up
	 * @param e
	 */
	public void add(E e) {
		// 将新增元素加到最末尾。
		data.add(e);
		// 堆的调整，让其满足最大堆性质。
		siftUp(data.size() - 1);
	}
	
	private void siftUp(int index) {
		assert index >= 0;
		assert index < data.size();
		// 当前节点大于其父节点，进入循环继续调整，直到当前节点小于父节点或者已经成为根节点
		while (index > 0 && data.get(parentIndex(index)).compareTo(data.get(index)) < 0) {
			swap(parentIndex(index), index);
			// 更新当前节点的索引
			index = parentIndex(index);
		}
	}
	
	/**
	 * 单纯获取最大值，不删除
	 * @return
	 */
	public E findMax() {
		assert data.size() > 0;
		return data.get(0);
	}
	
	/**
	 * 从最大堆中提取出最大的元素，sift down
	 * @return
	 */
	public E extractMax() {
		E ret = findMax();
		// 将最末尾的元素放到根节点上。
		swap(0, data.size() - 1);
		data.remove(data.size() - 1);
		siftDown(0);
		return ret;
	}
	
	private void siftDown(int index) {
		while (leftChildIndex(index) < data.size()) {
			// 取得左子节点索引
			int j = leftChildIndex(index);
			if (j + 1 < data.size() && data.get(j + 1).compareTo(data.get(j)) > 0) {
				// 当前节点有右子节点，并且右子节点的值大于左子节点的值
				// 将 j 更新为右子节点的索引
				j += 1;
			}
			if (data.get(index).compareTo(data.get(j)) >= 0) {
				// 当前节点大于较大值，符合最大堆性质，无需再 siftDown
				break;
			}
			// 交换当前节点与较大值交换。
			swap(index, j);
			// 更新当前节点索引
			index = j;
		}
	}
	
	/**
	 * 交换两个节点的值
	 * @param parent
	 * @param child
	 */
	private void swap(int parent, int child) {
		assert parent >= 0;
		assert parent < data.size();
		assert child >= 0;
		assert child < data.size();
		E temp = data.get(parent);
		data.set(parent, data.get(child));
		data.set(child, temp);
	}
	
}